As the name implies, cellular networks are made up of many separate cells. Commonly, cells are grouped into mobile switching center (MSC) domains in order to route calls between individual cells and the remainder of a wireless network (e.g., cellular, Personal Communications System (PCS), etc.). When a user of a wireless device (e.g., cell phone, pager or PDA) moves from one location to another, the network must track her location, or more precisely, the location of her mobile device. Typically, there are thousands of such movements each second in a modern wireless network. A wireless network tracks the number of such movements and associates a network cost to them. This cost is referred to as an updating cost.
While updating costs are associated with tracking the movement of users, other costs, referred to as paging costs, are associated with finding users. For example, when one user sends a call from one wireless network to a user within another wireless network, the receiving network must identify and locate the intended recipient of the call within its many cells. Typically, existing wireless networks send a page to each cell within an MSC where the recipient might be located. For example, if there are 100 cells within an MSC, a typical wireless network will send a page to all 100 cells even though the recipient is located in only one of the cells. The network tracks these pages and assigns a paging cost to each page.
Owners, operators and others involved in wireless networks desire to minimize or reduce the updating and paging costs associated with their networks. To do so, it is desirable to devise techniques which partition or group cells in such a way that both updating and paging costs are minimized. This has been a daunting challenge for it has been thought that even the mathematical statements (i.e., equations), which represent the problem have, heretofore, only been hypothetically solvable using exhaustive searches/iterations (none have actually been completed).
Finding a way to partition cells is a “balancing act” of sorts. Ideally, updating costs could be minimized by limiting the number of so-called “location area boundaries” that a user traverses when she moves from place to place. One way of doing this is to include every cell in one large “location area” (LA). As one might surmise, while this minimizes updating costs, it greatly increases paging costs because the larger the number of cells, the larger the number of pages that must be sent. The reverse is also true (i.e., creating new location areas by removing cells from an original location area may decrease paging costs but increase updating costs).
To date, though some have been able to formulate mathematical equations representing the parameters involved in partitioning cells, none have been able to guarantee that their solutions are efficient.